package leetcode_400;

/**
 *@author 周杨
 *SuperPow_372 求一个数的超级数幂	
 *describe:数学欧拉公式 AC 100%
 *2018年7月9日 下午1:33:45
 */
public class SuperPow_372 {
	/**
	 * describe:欧拉数学公式 AC 100%	
	 * 2018年7月9日 下午1:33:32
	 */
	public int superPow(int a, int[] b) {
		if (a % 1337 == 0)
			return 0;
		int p = 0;
		for (int i : b)
			p = (p * 10 + i) % 1140;
		if (p == 0)
			p += 1440;
		return power(a, p, 1337);
	}

	public int power(int a, int n, int mod) {
		a %= mod;
		int ret = 1;
		while (n != 0) {
			if ((n & 1) != 0)
				ret = ret * a % mod;
			a = a * a % mod;
			n >>= 1;
		}
		return ret;
	}
	
	
	/*public int superPow1(int a, int[] b) {快速幂算法
	       int c=1337;
	    int ans = 1;
	    a = a % c;
	    while(b>0){
	    if(b % 2 == 1)
	        ans = (ans * a) % c;
	            b = b/2;
	        a = (a * a) % c;
	            }
	    }*/
}
